// 解题思路：
// 题目要求重构字符串，要求相同字母不相邻
// 定义返回值数组，用于放重拍的字符
// 优先处理：找到出现次数最多的字符，从 0 下标开始放，隔一个下标，放一个
// 放剩余的字符，接着上面的位置，隔一个放一个，如果放到最后超出数组的长度，从下标 1 开始放
// 注意：如果出现次数最多的字符个数超过了数组的 (n + 1) / 2，则没法排列，返回空串即可

public class Solution {
    public String reorganizeString(String s) {
        char[] sArr = s.toCharArray();
        int n = sArr.length;
        int[] hash = new int[26];

        for(char ch : sArr) hash[ch - 'a']++;

        int max = 0;
        int maxPos = 0;
        for(int i = 0; i < 26; i++) {
            if(max < hash[i]) {
                max = hash[i];
                maxPos = i;
            }
        }

        if(max > (n + 1) / 2) return "";

        char[] ret = new char[n];
        int pos = 0;
        while(max-- > 0){
            ret[pos] = (char)('a' + maxPos);
            pos += 2;
        }

        for(int i = 0; i < 26; i++){
            if(i != maxPos && hash[i] != 0) {
                int value = hash[i];
                char ch = (char)('a' + i);

                while(value-- > 0){
                    if(pos >= n) pos = 1;
                    ret[pos] = ch;
                    pos += 2;
                }
            }
        }

        return new String(ret);
    }
}
